package com.freedy.dataStructure.sort;


import java.util.Arrays;

/**
 * @author Freedy
 * @date 2021/3/18 21:42
 */
public class ShellSort {
    public static void main(String[] args) {
        //20个随机数
        int[] arr={368,93,284,507,204,620,331,573,910,977,
                711,305,825,438,698,49,868,241,598,737};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }


    /**
     * 优化后
     */
    public static void sort(int[] arr) {
        for (int gap = arr.length/2; gap > 0; gap /=2) {
            for (int i = gap; i <  arr.length; i++) {
                int temp=arr[i];
                for (int j = i-gap; j >=0 ; j-=gap) {
                    if (temp<arr[j]){
                        arr[j+gap]=arr[j];
                        arr[j]=temp;
                    }else {
                        break;
                    }
                }
            }
        }
    }

    /**
     * 优化前
     */
    public static void beforeOptimizationSort(int[] arr) {
        for (int gap = arr.length/2; gap > 0; gap /=2) {
            //对每组进行排序
            for (int i = 0; i < gap; i++) {
                //采用插入排序法对此组数据排序
                for (int j = i; j < arr.length; j = j + gap) {
                    for (int k = i; k < j; k = k + gap) {
                        if (arr[j]<arr[k]){
                            int temp=arr[j];
                            for (int l = 0; l <(j-k)/gap; l++) {
                                arr[j-l*gap]=arr[j-(l+1)*gap];
                            }
                            arr[k]=temp;
                            break;
                        }
                    }
                }
            }
        }
    }
}


